/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/edit-distance
   @Language: C++
   @Datetime: 19-07-04 09:45
   */

class Solution {
public:
	int minDistance(string &word1, string &word2) {
		if(word1.length()<word2.length()) return minDistance(word2,word1);
		int m=word1.length(), n=word2.length();
		vector<vector<int> > dp(2,vector<int>(n+1,0));
		for(int i=n+1; i--; dp[0][i]=i);
		for(int i=1; i<=m; ++i){
			dp[i&1][0]=i;
			for(int j=1; j<=n; ++j){
				int replace=dp[(i-1)&1][j-1]+(word1[i-1]==word2[j-1]?0:1);
				int insert=dp[i&1][j-1]+1;
				int deletion=dp[(i-1)&1][j]+1;
				dp[i&1][j]=min(replace,min(insert,deletion));
			}
		}
		return dp[m&1][n];
	}
};
